Conversion de postfixe en préfixe

Objectif

Votre objectif est de convertir une expression expression postfixe (notation polonaise inversée) en son équivalent expression préfixe (notation polonaise) en construisant et en parcourant un arbre d'expression.

Algorithme

1. Construire l'arbre d'expression : Traitez l'expression postfixe de gauche à droite en utilisant une pile.
   • Lorsqu'un opérande (par exemple, A, B) est trouvé, créez un arbre à un seul nœud pour lui et placez-le sur la pile.
   • Lorsqu'un opérateur (par exemple, +, *) est trouvé, retirez deux arbres de la pile. Le premier retiré est le fils droit (T₂) et le second est le fils gauche (T₁). Créez un nouvel arbre avec l'opérateur comme racine et remettez-le sur la pile.
2. Générer la chaîne préfixe : Après avoir traité tous les symboles, la pile contiendra l'arbre d'expression complet. Effectuez un parcours en préordre (Racine → Gauche → Droite) sur cet arbre pour produire l'expression préfixe finale.

Exemple

Pour l'expression postfixe A B + C *, l'algorithme construit l'arbre suivant :

  *
   / \
  +   C
 / \
A   B

Un parcours en préordre donne l'expression préfixe : * + A B C.

Format Entrée/Sortie

Entrée

• Ligne 1 : Un entier N (1 ≤ N ≤ 1000), le nombre de symboles.
• Ligne 2 : L'expression postfixe, avec N symboles séparés par des espaces.

Règles des symboles

• Opérandes : Lettres majuscules simples (A-Z).
• Opérateurs : Les quatre opérateurs binaires : +, -, *, /.

Sortie

• Une seule ligne contenant l'expression préfixe correspondante, avec les symboles séparés par des espaces.

Exemples

Exemple 1 :

5

A B + C *

* + A B C

Exemple 2 :

7

A B C * + D /

/ + A * B C D

Exemple 3 :

7

A B + C D - *

* + A B - C D

Limites